package com.tgy.algorithm.base._排序;

import java.util.Arrays;

public class _快速排序_02 {

    public static void quickSort(int[] nums) {
        doQuickSort(nums,0,nums.length - 1);
    }

    public static void doQuickSort(int[] nums,int left,int right) {
        if (left >= right) {
            return;
        }

        int povit = nums[right];
        // leftIndex 小于povit
        int leftIndex = left - 1;
        // rightIndex +1 是大于 povit
        int rightIndex = right - 1;
        int curIndex = left;

        while (curIndex <= rightIndex) {
            int value = nums[curIndex];
            if (value < povit) {
                if (leftIndex+1 != curIndex) {
                    swap(nums,leftIndex+1,curIndex);
                }
                curIndex++;
                leftIndex++;
            }else if(value == povit) {
                curIndex++;
            }else {
                swap(nums,rightIndex,curIndex);
                rightIndex--;
            }
        }

        // [xx,]
        swap(nums,rightIndex+1,right);

        doQuickSort(nums,left,leftIndex);
        doQuickSort(nums,rightIndex+2,right);
    }

    public static void swap(int[] nums,int one,int two) {
        int tmp = nums[one];
        nums[one] = nums[two];
        nums[two] = tmp;
    }

    public static void main(String[] args) {
        int[] nums = new int[]{3,2,12,3,4,1,2,3,4};
        quickSort(nums);
        System.out.println(Arrays.toString(nums));
    }
}
